1561C - Deep Down Below - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll int
const int mod=1e9+7;
// vector<vector<int>>graph;
// vector<bool>visited;
// vector<int>level;
// int bfs(ll x,ll b) {
//     queue<int> q;
//     visited[x] = true;
//     q.push(x);
//     level[x]=0;
//     while(!q.empty()) {
//         x = q.front();
//         q.pop();
//         int n = graph[x].size();
//         for(int i=0; i<n; i++) {
//             if(!visited[graph[x][i]]) {
//                 visited[graph[x][i]]=true;
//                 level[graph[x][i]]=level[x]+1;
//                 if(graph[x][i]==b){
//                     return level[b];
//                 }
//                 q.push(graph[x][i]);
//             }
//         }

//     }
//     return -1;
// }

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
   cerr << '{';
   __print(x.first);
   cerr << ',';
   __print(x.second);
   cerr << '}';
}
template <typename T>
void __print(const T &x)
{
   int f = 0;
   cerr << '{';
   for (auto &i : x)
      cerr << (f++ ? "," : ""), __print(i);
   cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
   __print(t);
   if (sizeof...(v))
      cerr << ", ";
   _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)              \
   cerr << "[" << #x << "] = ["; \
   _print(x)
#else
#define debug(x...)
#endif

ll n;
vector<ll>prefix;
vector<pair<int,int>>v1;
// vector<ll>v2;

// ll bin_search(ll x){
//    ll l=-1;
//    ll r=v2.size();
//    while(r-l>1){
//       ll m=(l+r)/2;
//       if(v2[m]>=x)
//       r=m;
//       else
//       l=m;
//    }
//    return v2[r];
// }

int32_t main()
{
     ios_base :: sync_with_stdio(false);
     cin.tie(NULL);cout.tie(NULL);

     ll t;cin>>t;
     while(t--){
         cin>>n;
         prefix.clear();
         prefix.resize(n+1);
         //v2.clear();
         v1.clear();
         prefix[0]=0;
         for(ll i=0;i<n;i++){
            ll x;
            cin>>x;
            ll bada=INT_MIN;

            for(ll j=0;j<x;j++){
               ll a;
               cin>>a;
               bada=max(bada,a-j);
            }
            v1.push_back({bada+1,x});
         }

         sort(v1.begin(),v1.end());
         debug(v1);

         for(ll i=1;i<=n;i++){
            prefix[i]=prefix[i-1]+v1[i-1].second;
         }

         debug(prefix);

         // ll i=v1[0].first;
         // while(i<=v1[n-1].first){
         //    v2.push_back(i);
         //    i++;
         // }

         if(n==1){
         cout<<v1[0].first<<endl;
         continue;}
         ll ans=v1[0].first;
         for(ll i=2;i<=n;i++){
            ll x=(v1[i-1].first-prefix[i-1]);
            ans=max(x,ans);
         }

         cout<<ans<<endl;
      }
}